/*
题目: 分数加减运算
给定一个表示分数加减运算的字符串 expression ，你需要返回一个字符串形式的计算结果。

这个结果应该是不可约分的分数，即最简分数。 如果最终结果是一个整数，例如 2，你需要将它转换成分数形式，其分母为 1。所以在上述例子中, 2 应该被转换为 2/1。

https://leetcode.cn/problems/fraction-addition-and-subtraction
 */
public class FractionAddition {
    int n = 0;

    public String fractionAddition(String expression) {
        n = expression.length();
        int num = searchNum(expression); //分数个数

        int[] child = new int[num]; //分别负责记录分子和分母
        int[] parent = new int[num];
        int k = 0; //记录下标

        int i = 0;
        while (i < n) {
            int isPositive = 1;
            while (i < n && expression.charAt(i) != '/') { //找分子
                char ch = expression.charAt(i++);
                if (ch == '-') {
                    isPositive *= -1;
                    continue;
                }
                if (Character.isDigit(ch)) {
                    child[k] = child[k] * 10 + (ch - '0');
                }
            }
            child[k] *= isPositive;
            i ++; //跳过分数线
            while (i < n && Character.isDigit(expression.charAt(i))) {
                parent[k] = parent[k] * 10 + (expression.charAt(i++) - '0');
            }
            k++;
        }

        //寻找分母的最小公倍数
        i = 0;
        int prev = parent[i];
        for (i = 1; i < num; i ++) {
            prev = lcm(prev, parent[i]);
        }
        //然后让分子经过处理后, 全部相加
        int sum = 0;
        for (i = 0; i < num; i++) {
            sum += child[i] * (prev / parent[i]);
        }

        int tmp =Math.abs(gcd(sum, prev));  //分子分母的最小公倍数, 保证不为负
        sum /= tmp; //同除最小公倍数
        prev /= tmp;
        if (sum == 0)   prev = 1; //特殊情况特殊处理
        String result = String.valueOf(sum) + "/" +  String.valueOf(prev);
        return result;
    }

    private int lcm(int a, int b) { //求两个数的最小公倍数
        return a * b / gcd(a, b);
    }

    private int gcd(int a, int b) { //求两个数的最大公倍数
        while (b != 0) {
            int tmp = b;
            b = a % b;
            a = tmp;
        }
        return a;
    }

    private int searchNum(String expression) {
        int ret = 0;
        for (int i = 0; i < n; i++) {
            if (expression.charAt(i) == '/') {
                ret++;
            }
        }
        return ret;
    }
}
